#include<stdio.h>
#include<iostream>
using namespace std;

void Print(int A[], int n) {
	for (int i = 0; i < n; ++i) {
		cout << A[i] << " ";
	}cout << endl;
}

//排序
void SpliceArrary1(int A[], int n) {
	for (int i = 0; i < n - 1; ++i) {
		for (int j = i + 1; j < n; ++j) {
			if (A[i] > A[j]) {
				int tmp = A[i];
				A[i] = A[j];
				A[j] = tmp;
			}
		}
	}

	int s1 = 0, s2 = 0;
	for (int i = 0; i < n / 2; ++i)
		s1 += A[i];
	for (int i = n / 2; i < n; ++i)
		s2 += A[i];
	
	Print(A, n);
	cout << abs(s1 - s2) << endl;
}

//快排思想
void SpliceArrary2(int A[], int n) {
	int low = 0, high = n - 1, left = 0, right = n - 1;
	int k = n / 2 - 1;
	while (1) {
		int key = A[low];
		while (low < high) {
			while (low < high && key <= A[high])
				high--;
			A[low] = A[high];

			while (low < high && key >= A[low])
				low++;
			A[high] = A[low];
		}
		A[low] = key;

		if (low == k)
			break;

		if (low < k) {
			left = ++low;
			high = right;
		}
		else {
			low = left;
			right = --high;
		}

	}
	Print(A, n);
	int s1 = 0, s2 = 0;
	for (int i = 0; i < n / 2; ++i)
		s1 += A[i];
	for (int i = n / 2; i < n; ++i)
		s2 += A[i];
	cout << abs(s1 - s2) << endl;
}

int main() {
	int A[] = { 0,7,4,8,2,1,3,5,6,9 };
	int n = sizeof(A) / sizeof(A[0]);
	SpliceArrary1(A, n);
	SpliceArrary2(A, n);
	return 0;
}